In order to accelerate the processing of data, many high-performance computing systems are controlled by a single-instruction stream yet operate on multiple-data streams (SIMD). One such computing system is a vector computer designed to process in parallel each element of a linear array of numbers. For example, a vector machine adds two vectors by adding in parallel each entry of the two vectors to produce a single vector of the same length. A single vector instruction is therefore equivalent to a programming loop iterating from 1 to the number of elements in the vector.
Wherever possible, a specialized compiler replaces programming loops with vector instructions. Whether a compiler can vectorize a loop often depends on whether each element in a result vector can be computed independently from the other elements. When the results of one iteration of the loop depend on results of previous iterations, a data hazard exists and the loop typically cannot be "vectorized". The extent that a program can be vectorized, however, not only depends on the existence of data hazards but on the ability of the compiler to restructure the program in order to reduce or eliminate the data dependencies. Thus, there is tremendous variation the software routines that conventional compilers can vectorize.
One class of software that conventional compilers have difficulty vectorizing is inductive loops having conditional statements. Typical examples of this class of software includes vector compression and vector expansion. In vector compression, elements of a source vector are copied to a destination vector based on some condition such as a mask bit. Thus, only a subset of the elements of the source vector are copied to the destination vector and are stored in the lower order elements of the destination vector. Because the destination of a particular source element depends on how many elements need to be copied, a data hazard exists that prevents the compression from easily being vectorized. Similar problems exist for vector expansion.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for a method and system for operating a computer having multiple processing unit that easily vectorize inductive loops having conditional statements. There is also a need for an optimizing compiler which can generate machine instructions for such a computer system.